package leetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Q199 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> mat = new ArrayList<>();

        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        if(root == null) return res;
        deque.add(root);
        while (deque.size()!=0){
            //上一层的元素个数
            int n = deque.size();
            ArrayList<Integer> integers = new ArrayList<>();

            for(int i=0;i<n;i++){
                TreeNode node = deque.removeFirst();
                if(node.left!=null)
                    deque.addLast(node.left);
                if(node.right!=null)
                    deque.addLast(node.right);
                integers.add(node.val);
            }
            mat.add(integers);
        }

        if(mat.size()>0){
            for (List<Integer> integers : mat) {
                res.add(integers.get(integers.size()-1));
            }
        }

        return res;
    }

}


